﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm
{
    internal class MergeSort
    {

        /// <summary>
        /// 合并排序，非原地排序，时间复杂度为 n* lgn
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        public static void MergeSortArray<T>(T[] array, int start, int end) where T : IComparable<T>
        {
            if (start < end)
            {
                int q = (start + end) / 2;
                MergeSortArray<T>(array, start, q);
                MergeSortArray<T>(array, q + 1, end);
                Merge<T>(array, start, q, end);
            }
        }

        /// <summary>
        /// 合并两个排好序的子数组array[p..q],array[q+1..r]
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <param name="r"></param>
        private static void Merge<T>(T[] array, int p, int q, int r) where T : IComparable<T>
        {
            int childArrayLength1 = q - p + 1;
            int childArrayLength2 = r - q;

            T[] childArray1 = Copy<T>(array, p, childArrayLength1);
            T[] childArray2 = Copy<T>(array, q + 1, childArrayLength2);

            int child1Index = 0;
            int child2Index = 0;
            bool child1Over = false;
            bool child2Over = false;
            for (int i = p; i <= r; i++)
            {

                if (!child1Over && (child2Over || childArray1[child1Index].CompareTo(childArray2[child2Index]) <= 0))
                {
                    array[i] = childArray1[child1Index];
                    child1Index++;
                    child1Over = child1Index >= childArrayLength1;
                }
                else if (!child2Over)
                {
                    array[i] = childArray2[child2Index];
                    child2Index++;
                    child2Over = child2Index >= childArrayLength2;
                }
            }
        }

        /// <summary>
        /// 复制数组元素
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        /// <param name="start"></param>
        /// <param name="length"></param>
        /// <returns></returns>
        private static T[] Copy<T>(T[] array, int start, int length)
        {
            T[] result = new T[length];
            for (int i = 0; i < length; i++)
            {
                result[i] = array[start + i];
            }

            return result;
        }
    }
}
